package com.ftg.learn.chapter17.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 树形结构 ：
 *  实现搜索二叉树的功能
 *  - 针对常用功能，主体完成二叉树功能
 *  - 构造方法
 *  - 添加方法 ： 递归
 *  - 遍历 ：
 *      -- 先序：
 *      -- 中序：
 *      -- 后序：
 * @author KangJx
 * @date 2021/8/8
 */
public class BinaryTree {


    /**
     * 遍历以后返回的相应的节点，用list让大家看得更清楚
     */
    private List<TreeNode> order;

    /**
     * 根结点 ： 回想一下我们写过的单链表
     */
    private TreeNode root;

    public BinaryTree(){
        order = new ArrayList<>();
        order.clear();
    }

    /**
     * 私有递归方法，为了实现特定树
     *  - 左子树 小于 根节点
     *  - 右子树 大于 根节点
     * @param current  根据当前节点查找
     * @param value    节点数据
     * @return
     */
    private TreeNode addNode(TreeNode current, int value) {
        //初始节点
        if (current == null) {
            return new TreeNode(value);
        }
        //递归添加左子树
        if (value < current.data) {
            current.left = addNode(current.left, value);
            //右子树
        } else if (value > current.data) {
            current.right = addNode(current.right, value);
        } else {
            //当前节点
            return current;
        }
        return current;
    }

    /**
     * 添加功能实现，为树添加节点
     * @param value 节点存储的数据
     */
    public void addNode(int value) {
        root = addNode(root, value);
    }

    /**
     * 查找节点 ，递归查找
     * - 查找二叉树
     *  --左子树的内容永远比父节点小
     *  --右子树的内容永远比父节点大
     *  -- 所以我们想用递归来查找 ， 如果当前节点的内容 小于 value 那么就查找当前节点的左节点，依次
     * @param current  当前节点
     * @param value    当前节点数据
     * @return
     */
    private boolean containNode(TreeNode current, int value) {
        if (current == null) {
            return false;
        }
        if (value == current.data) {
            return true;
        }
        return value < current.data ? containNode(current.left, value) : containNode(current.right, value);
    }

    /**
     * 对外开放的方法，用于对外使用，查找数值是否在搜索二叉树上
     * @param value  内容
     * @return
     */
    public boolean containNode(int value) {
        return containNode(root, value);
    }

    /**
     * 删除某个节点，根据
     * @param current
     * @param value
     * @return
     */
    public TreeNode deleteNode(TreeNode current, int value) {
        //当前节点为空
        if (current == null) {
            return null;
        }
        //如果当前节点就是与value内容相等
        if (value == current.data) {
            if (current.left == null && current.right == null) {
                return null;
            }
            if (current.left == null) {
                return current.right;
            }
            if (current.right == null) {
                return current.left;
            }
            int smallestValue = findSmallestValue(current.right);
            current.data = smallestValue;
            current.right = deleteNode(current.right, smallestValue);
            return current;
        }
        if (value < current.data) {
            current.left = deleteNode(current.left, value);
            return current;
        }
        current.right = deleteNode(current.right, value);
        return current;
    }

    private int findSmallestValue(TreeNode root) {
        return root.left == null ? root.data : findSmallestValue(root.right);
    }

    /**
     * 先序遍历:pre-order
     * parent->left->right
     */
    public List<TreeNode> preOrder(TreeNode node){
        if( node == null ){
            //啥也没有
            return null;
        }
        //输出
        this.order.add(node);
        preOrder(node.left);
        preOrder(node.right);
        return order;
    }

    /**
     * 中序遍历 inorder
     * left - parent - right
     * @param root
     */
    public List<TreeNode> traverseInOrder(TreeNode root) {
        if (root != null) {
            traverseInOrder(root.left);
            this.order.add(root);
            traverseInOrder(root.right);
        }
        return this.order;
    }

    /**
     * 后序遍历
     *  指定节点
     */
    public List<TreeNode> postOrderTraversal(TreeNode node) {
        if (node.left != null) {
            postOrderTraversal(node.left);
        }
        if (node.right != null) {
            postOrderTraversal(node.right);
        }
        this.order.add(node);
        return this.order;
    }


    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    /**
     * 生成二叉树,用来测试使用
     * @return
     */
    public static BinaryTree createBinaryTree() {
        BinaryTree bt = new BinaryTree();
        bt.addNode(6);
        bt.addNode(4);
        bt.addNode(8);
        bt.addNode(10);
        return bt;
    }

    public static void main(String[] args) {
        //初始化方法
        BinaryTree bt = createBinaryTree();
        //查找
        boolean ist = bt.containNode(10);
        System.out.println(ist);

        //删除
        bt.deleteNode(bt.getRoot(),10);

//        System.out.println("先序遍历");
//        List<TreeNode> list = bt.preOrder(bt.getRoot());
//        list.forEach(t ->{
//            System.out.println(t.data);
//        });
//
//        System.out.println("中序遍历");
//        List<TreeNode> inorder = bt.traverseInOrder(bt.getRoot());
//        inorder.forEach(t->{
//            System.out.println(t.data);
//        });
//
//        System.out.println("后序遍历");
//        List<TreeNode> postorder = bt.postOrderTraversal(bt.getRoot());
//        postorder.forEach(t->{
//            System.out.println(t.data);
//        });
    }

    /**
     * 定义树的 节点对象
     * data:   数值
     * left：  左子树
     * right： 右子树
     */
    public class TreeNode {

        int data;
        TreeNode left;
        TreeNode right;

        public TreeNode(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

}
